//题目:
// 在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。
// mines[i] = [xi, yi]表示 grid[xi][yi] == 0
// 返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

// 一个k阶由1组成的 “轴对称”加号标志,具有中心网格 grid[r][c] == 1 ，
// 以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。
// 注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//代码
class Solution 
{
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) 
    {
        //1.创建dp表————f[i][j]表示：以nums[i][j]为中心网格的右、下行中连续1的最小数目
        vector<vector<int>> lt(n,vector<int>(n,1));//lt[i][j]表示：以nums[i][j]为中心网格的左边中连续1的最小数目
        vector<vector<int>> rt(n,vector<int>(n,1));//rt[i][j]表示：以nums[i][j]为中心网格的右边中连续1的最小数目
        vector<vector<int>> on(n,vector<int>(n,1));//on[i][j]表示：以nums[i][j]为中心网格的上边中连续1的最小数目
        vector<vector<int>> below(n,vector<int>(n,1));//below[i][j]表示：以nums[i][j]为中心网格的下边中连续1的最小数目
        //2.初始化
        for(int i=0;i<mines.size();i++){
            int x=mines[i][0],y=mines[i][1];
            lt[x][y]=rt[x][y]=on[x][y]=below[x][y]=0;
        }
        //3.填表：计算nums[i][j]的上、下、左、右四个方向的连续1的个数
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<n;j++)
            {
                //计算nums[i][j]的左、上两个方向连续1的个数
                if(lt[i][j]==1) lt[i][j]+=lt[i][j-1],on[i][j]+=on[i-1][j];
            }
        }
        for(int i=n-2;i>=0;i--)
        {
            for(int j=n-2;j>=0;j--)
            {
                //计算nums[i][j]右、下两个方向连续1的个数
                if(rt[i][j]==1) rt[i][j]+=rt[i][j+1],below[i][j]+=below[i+1][j];
            }
        }
        int ret=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                //计算nums[i][j]四个方向上连续1的最小个数，即加号标志的阶级数
                if(lt[i][j]!=0) ret=max(ret,min({lt[i][j],rt[i][j],on[i][j],below[i][j]}));
            }
        }
        return ret;
    }
};